package com.hackerrank.bipartite;

import java.util.Scanner;

public class BipartiteMatching {
	private static int GCD(int a, int b) {
		return GCDmm(Math.min(a, b), Math.max(a, b));
	}
	private static int GCDmm(int m, int M) {
		if(m == 0)
			return M;
		return GCDmm(M % m, m);
	}
    public static void main(String[] args) {
		// scan input
		Scanner in = new Scanner(System.in);
		int N = in.nextInt(), A[] = new int[N], B[] = new int[N];
		for(int i = 0; i < N; i++)
			A[i] = in.nextInt();
		for(int i = 0; i < N; i++)
			B[i] = in.nextInt();
		
		// calculate matchings
        int s = 2*N, t = 2*N + 1;
        FlowNetwork G = new FlowNetwork(2*N + 2);
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++)
				if(GCD(A[i], B[j]) > 1)
					G.addEdge(new FlowEdge(i, j + N, Double.POSITIVE_INFINITY));
		
        for (int i = 0; i < N; i++) {
            G.addEdge(new FlowEdge(s,     i, 1.0));
            G.addEdge(new FlowEdge(i + N, t, 1.0));
        }

        // compute maximum flow and minimum cut
        FordFulkerson maxflow = new FordFulkerson(G, s, t);
        System.out.println((int) maxflow.value());
    }
}
